/*
 *  Blazon: A user datagram protocol re-braodcasting daemon.
 *  hash.c: Hash table functions and support.
 *
 *  Copyright 2012 Blazon development team
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 2 of the License, or
 *  (at your option) any later version.

 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.

 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "std-include.h"

#include <math.h>

#include "hash.h"
#include "log.h"
#include "tools.h"


struct hashtable * hashtable_create(unsigned short);
uint32_t hash_index(struct hashtable *, const unsigned char *s);
bool hashnode_add(struct hashtable *, void *, void *);
void * hash_find_delete(struct hashtable *, void *);
void * hashnode_find(struct hashtable *, void *);
bool hashnode_update(struct hashtable *, void *, void *);
void hashtable_destroy(struct hashtable *, short);
void * hashnode_delete(hash_node *, hash_node **);
static bool hashtable_expand(struct hashtable *);


struct hashtable *
hashtable_create(unsigned short bitsize)
{
	struct hashtable *hash_t;

	/* Check requested hashtable isn't too small or large */
	if (bitsize < 8 || bitsize > 20)
		return NULL;

	hash_t = my_malloc(sizeof(struct hashtable));
	if (hash_t == NULL)
		return NULL;

	/* Going to make an array of dlink_lists */
	hash_t->table = my_malloc(sizeof(hash_node *) * (1 << bitsize));

	hash_t->bitsize = bitsize;
	hash_t->count = 0;
	hash_t->keylen = KEYLEN;
	hash_t->loadlimit = (unsigned int) ceil((1<<bitsize) * MAX_LOAD_FACTOR);

	return hash_t;
}


/*
 * Hash function derived from ircd-ratbox.
 * Copyright (C) 1990 Jarkko Oikarinen and University of Oulu, Co Center
 * Copyright (C) 1996-2002 Hybrid Development Team
 * Copyright (C) 2002-2012 ircd-ratbox development team
 */
uint32_t
hash_index(struct hashtable *hash_t, const unsigned char *s)
{
	uint32_t h = FNV1_32_INIT;
	uint32_t bits = 32 - hash_t->bitsize;
	const unsigned char *x = s + hash_t->keylen;

	while(*s && s < x)
	{
		h ^= *s++;
		h += (h << 1) + (h << 4) + (h << 7) + (h << 8) + (h << 24);
	}
	h = (h >> bits) ^ (h & ((2 ^ bits) - 1));
	return h;
}


/* This function just adds new hash nodes, it doesn't check to see
 * whether a entry already exists with the same key_string.
 */
bool
hashnode_add(struct hashtable *ht, void *key, void *data)
{
	unsigned int idx;
	hash_node *new_node;

	if(ht->count >= ht->loadlimit)
		hashtable_expand(ht);

	idx = hash_index(ht, key);

	new_node = my_malloc(sizeof(hash_node));

	strlcpy(new_node->key, key, ht->keylen);
	new_node->data = data;

	if(ht->table[idx] == NULL)
	{
		ht->table[idx] = new_node;
		/*log_info("Node '%s' added as head (%d)", key, idx);*/
	}
	else
	{
		/* Stick new node at the head of the list (not the tail) */
		new_node->next = ht->table[idx];
		ht->table[idx] = new_node;
		/*log_info("Node '%s' appended to (%d)", key, idx);*/
	}

	ht->count++;

	return true;
}


/* Searches for and removes a hash node from the table. Node's data
 * is returned for caller do handle.
 */
void *
hashnode_find_delete(struct hashtable *ht, void *key)
{
	unsigned int idx;
	hash_node *ptr, *prev_node;
	void *data;

	if (!ht || ht->count == 0)
		return NULL;

	idx = hash_index(ht, key);

	/* Refer to the previous node, which at the beginning of the list
	 * is actually the first node.
	 */
	prev_node = ht->table[idx];

	for(ptr = ht->table[idx]; ptr != NULL; ptr = ptr->next)
	{
		if (strncmp(key, ptr->key, ht->keylen) == 0)
		{
			/* Get the data before deleting so we can return it */
			data = ptr->data;

			/* Doesn't matter if this is NULL or not, we still
			 * want the value to bypass the node we're deleting.
			 */
			if (ptr == ht->table[idx])
				ht->table[idx] = ptr->next;
			else
				prev_node->next = ptr->next;

			/* This node matches, delete it. */
			my_free(ptr);

			log_info("Deleting node '%s' from bucket %d", key, idx);
			ht->count--;
			return data;
		}

		prev_node = ptr;
	}

	/* Matching node doesn't exist at this hash index, return NULL */
	return NULL;
}


/* Helper function to delete a hash_node. Hash node is passed as an argument
 * pointer avoiding the need to compare keys and search for it. Node memory
 * is free()d and data is returned to caller.
 */
void *
hashnode_delete(hash_node *ptr, hash_node **head)
{
	void *data;

	data = ptr->data;

	if (*head == ptr)
	{
		*head = ptr->next;
		my_free(ptr);
	}
	else
	{
		hash_node *tmp = *head;
		while (tmp->next != ptr)
			tmp = tmp->next;
		/* tmp should now be the node before the one we
		 * need to remove. */
		tmp->next = ptr->next;
		my_free(ptr);
	}

	return data;
}


/* Destroys all nodes that have the specified key. Note that nodes in a bucket
 * can have slightly different keys.
 * Side effects:
 *   This function assumes the node data consists of standard types and can be
 *   free()d in the usual manner.
 */
void
hashnode_destroy_all(struct hashtable *ht, void *key)
{
	unsigned int idx;
	hash_node *ptr, *prev;

	if (!ht)
		return;

	idx = hash_index(ht, key);

	/* Refer to the previous node, which at the beginning of the list
	 * is actually the first node.
	 */

	for(ptr = ht->table[idx], prev = ptr;
		ptr != NULL;
		prev = ptr ? ptr : prev, ptr = ptr ? ptr->next : prev->next)
	{
		if (strncmp(key, ptr->key, ht->keylen) == 0)
		{
			/* bypass current node with prev->next */
			if (ptr == ht->table[idx])
				ht->table[idx] = ptr->next;
			else
				prev->next = ptr->next;
			/* delete current node */
			my_free(ptr->data);
			my_free(ptr);
			/* give ptr the value of next node */
			ptr = NULL;

			log_debug("Destroying node '%s' (and data) from bucket %d", key, idx);
			ht->count--;
		}
	}
}


/* Searches the hashtable for a node matching 'key'. Returns a pointer
 * to whatever data the node was storing.
 */
void *
hashnode_find(struct hashtable *ht, void *key)
{
	unsigned int idx;
	hash_node *ptr;

	idx = hash_index(ht, key);

	for(ptr = ht->table[idx]; ptr != NULL; ptr = ptr->next)
	{
		if (strncmp(key, ptr->key, ht->keylen) == 0)
		{
			return ptr->data;
		}
	}

	return NULL;
}


/* Updates the data stored by a hash_node with the given struct.
 * If a hash_node matching the key does not exist, one is created.
 * Side-effects:
 *   This function assumes the struct being stored by an existing
 *   node contains only standard types and will free() that memory.
 */
bool
hashnode_update(struct hashtable *ht, void *key, void *data)
{
	unsigned int idx;
	hash_node *ptr;

	idx = hash_index(ht, key);

	for(ptr = ht->table[idx]; ptr != NULL; ptr = ptr->next)
	{
		if (strncmp(key, ptr->key, ht->keylen) == 0)
		{
			my_free(ptr->data);
			ptr->data = data;
			log_debug("Updating node '%s' in bucket %d", key, idx);
			return true;
		}
	}

	/* Node to update wasn't found, create one. */
	ptr = my_malloc(sizeof(hash_node));

	strlcpy(ptr->key, key, ht->keylen);
	ptr->data = data;

	if (ht->table[idx] == NULL)
	{
		ht->table[idx] = ptr;
		log_debug("Node update '%s' added as head (%d)", key, idx);
	}
	else
	{
		/* Stick new node at the head of the list (not the tail) */
		ptr->next = ht->table[idx];
		ht->table[idx] = ptr;
		log_debug("Node update '%s' appended to (%d)", key, idx);
	}

	ht->count++;
	return true;
}


/* This function can ONLY free data if the data struct contains simple types */
void
hashtable_destroy(struct hashtable *ht, short free_data)
{
	unsigned int i, t_len;
	hash_node *ptr, *prev_node;

	if (!ht)
		return;

	t_len = (1 << ht->bitsize);

	for(i = 0; i < t_len; i++)
	{
		ptr = ht->table[i];

		while(ptr != NULL)
		{
			prev_node = ptr;
			ptr = ptr->next;
			if (free_data)
				my_free(prev_node->data);
			my_free(prev_node);
			log_debug("Destroying node in bucket %d", i);
		}
	}
	my_free(ht->table);
	my_free(ht);
}


static bool
hashtable_expand(struct hashtable *ht)
{
	hash_node **new_hash_t;
	hash_node *ptr;
	unsigned int table_len, i, idx;

	/* Check table doesn't exceed working max of 20 bits */
	if (ht->bitsize == 20)
		return false;

	ht->bitsize++;		/* Increase table size */

	log_info("Hash table reached max load. Expanding to new size: %u", (1 << ht->bitsize));
	new_hash_t = my_malloc(sizeof(hash_node *) * (1 << ht->bitsize));

	table_len = (1 << (ht->bitsize-1));
	for(i = 0; i < table_len; i++)
	{
		while ((ptr = ht->table[i]) != NULL)
		{
			/* Set list head as the next node to bypass current */
			ht->table[i] = ptr->next;
			/* Calculate new hash index for current node */
			idx = hash_index(ht, (const unsigned char *)ptr->key);
			/* Check if index in new table is NULL */ 
			if (new_hash_t[idx] == NULL)
			{
				new_hash_t[idx] = ptr;
				ptr->next = NULL;
			}
			else
			{
				ptr->next = new_hash_t[idx];
				new_hash_t[idx] = ptr;
			}
		}
	}

	my_free(ht->table);
	ht->table = new_hash_t;
	ht->loadlimit = (unsigned int) ceil((1 << ht->bitsize) * MAX_LOAD_FACTOR);

	log_info("Completed hash table expansion");

	return true;
}

